Stochastic block model

A class of generative models assumes that the connectivity between nodes is determined by their block membership of them.

Assume a network with $N$ nodes. Each node $i$ has a block membership $z_i \in \{1, 2, \dots, k\}$. The block matrix $\mathbf{M} ~(k \times k)$ prescribes the connectivity between blocks either by setting the expected number of edges (canonical) or the exact number of edges (microcanonical).

History

It has a long history in social science and computer science. Holland1983stochastic introduced the name and concept.

Variations

Degree-corrected models

• Karrer2011stochastic

Mixed membership models

A “mixed-membership” model assumes that each node may have multiple hidden labels (see Overlapping community structure).

• Mixed Membership Stochastic Blockmodels - Airoldi2008mmsbm

References

• Community Detection and Stochastic Block Models - a review paper by Emmanuel Abbe
• http://arxiv.org/abs/1008.3926 - Stochastic blockmodels and Community structure in networks
• http://arxiv.org/abs/1403.2933 - Efficiently inferring Bipartite community structure.
• Blockmodeling techniques for complex networks
• Efficient discovery of overlapping communities in massive networks - Gopalan2012community